Rich experimental evidences show that one can better estimate users' unknown ratings with the aid of graph side information such as social graphs. However, the gain is not theoretically quantified. In this work, we study the binary rating estimation problem to understand the fundamental value of graph side information. Considering a simple correlation model between a rating matrix and a graph, we characterize the sharp threshold on the number of observed entries required to recover the rating matrix (called the optimal sample complexity) as a function of the quality of graph side information (to be detailed). To the best of our knowledge, we are the first to reveal how much the graph side information reduces sample complexity. Further, we propose a computationally efficient algorithm that achieves the limit. Our experimental results demonstrate that the algorithm performs well even with real-world graphs.

Summary of paper: The paper considers the problem of completing a binary rating matrix, and theoretically studies whether side information in terms of graphs among users or items aid in the matrix completion task. On a technical level, the study assumes that the users belong to two communities, and users in the same group rate all items identically (upto some noise). The community structure is further revealed by the side information in terms of a graph generated from stochastic block model. The paper derives the optimal sample complexity for rating estimation in terms of the expected number of ratings that needs to be seen to exactly recover the rating matrix. Review summary: The paper is a solid piece of theoretical work and clearly written.